class Solution {
    private:
        int cal(char& x1, char& x2){
            return (x1 - '0') * 10 + (x2 - '0');
        }
public:
    int numDecodings(string s) {
        vector<int>dp(s.length(), 0);
        if(s[s.length() - 1] == '0')dp[s.length() - 1] = 0;
        else dp[s.length() - 1] = 1;
        for(int i = s.length() - 2; i >= 0; i--){
            if(s[i] == '0')dp[i] = 0;
            else if(s[i + 1] == '0'){
                if(i < s.length() - 2 && cal(s[i], s[i + 1]) <= 26)dp[i] = dp[i + 2];
                else if(cal(s[i], s[i + 1]) <= 26)dp[i] = 1;
                else dp[i] = 0;
            }
            else if(cal(s[i], s[i + 1]) > 26)dp[i] = dp[i + 1];
            else {
                dp[i] = dp[i + 1];
                if(i < s.length() - 2)dp[i] += dp[i + 2];
                else dp[i]++;
            }
        }
        return dp[0];
    }
};
